//
//Created by ZYZ on 2020/6/10.
//
#include <stdio.h>
#include <stdlib.h>
#include "polynomial_linked_list.h"
#include "redefinition_linked_list.h"

//根据 a<、= 或 >b,分别返回-1、0 或 1
int cmp(term a, term b) { //expn : 指数
    if (a.expn == b.expn)
        return 0;
    else
        return (a.expn - b.expn) / abs(a.expn - b.expn);
}

void CreatPolyn(polynomial &poly_linklist, int param_count) {
    //输入 m 项的系数和指数，建立表示一元多项式的有序链表 P
    InitList(poly_linklist);
    Position head_pos = GetHead(poly_linklist);

    ElemType head_elem;
    head_elem.coef = 0.0;
    head_elem.expn = -1;
    SetCurElem(head_pos, head_elem);                     //设置头结点的数据为 e

    Position pos;                                           //不要使用 Position *，因为该局部变量的指针没初始化
    Link node;

    for (int i = 1; i <= param_count; ++i) {                //依次输入 m 个非客项
        printf("请输入第 %d 个结点的系数和指数(用空格分隔)", i);
        scanf("%f%d", &head_elem.coef, &head_elem.expn);
        if (!LocateElemP(poly_linklist, head_elem, pos, cmp)) {   //如果当前链表中不存在该指数项 ()
            // 因为 pos 指向的是 poly_linklist 中第一个该元素的 data.expn(指数) > head_elem 的位置，所以之后 InsFirstP() 插入结点会在 pos 之前，从而保证了链表结点 是按照 指数 由小到大 依次相加的的
            if (MakeNode(node, head_elem)) {
//                InsFirstP(pos, node);                      //生成结点并插人链表,书上调用的是这个方法，但是该方法没有 +len，导致后边判断 polynomial 是否为空失败
                InsFirstP(poly_linklist, pos, node);
                printf("开始生成结点 coef = %f, expn = %d 并插入链表 \n", node->data.coef, node->data.expn);
            }
        }
    }
}//CreatPolyn


//h 指向 L 的一个结点，把 h 当做头结点，将 s 所指结点插入在第一个结点之前
Status InsFirstP(LinkList &L, Link h, Link s) {
    s->next = h->next;
    h->next = s;
    if (h == L.tail)                                        //h 指向尾结点，此时尾结点的后边的结点时 s，所以这个尾结点不再是尾结点
        L.tail = h->next;                                   //修改尾指针，而 h->next = s
    L.len++;
    return OK;
}//InsFirst


//h 指向 L 的一个结点，把h当做头结点，删除链表中的第一个结点并以 q 返回。
//若链表为空 (h指向尾结点)，q = NULL，返回 FALSE
Status DelFirstP(LinkList &L, Link h, Link &q) {            //形参增加 L,因为需修改L
    q = h->next;                                            //为了让 q 返回删除的节点，所以赋值  *q = h->next;
    if (q) {                                                //链表非空
        h->next = q->next;                                  //跳过第一个节点
        if (!h->next)                                       //删除尾结点
            L.tail = h;                                     //修改尾指针 (如果 h->next 是空的，说明 h 是最后一个结点即尾结点）
        L.len--;
        return OK;
    } else
        return ERROR;                                       //链表空
}//DelFirst


//按有序判定函数 compare() 的约定，将值为 e 的结点插入或合并到升序链表 L 的适当位置，有序插入并合并
void OrderInsertMerge(LinkList & link_list, ElemType ele, int(*compare)(term, term)) {
    Position loc_pos, prior_pos;                                //loc_pos 表示和 ele 的指数相同的位置
    if (LocateElemP(link_list, ele, loc_pos, compare)) {    //L中存在该指数项则执行 if 语句块，否则会将 link_list 第一个满足 compare(该结点,ele) > 0 的结点前一个结点的位置赋值给 loc_pos，从而插入结点
        loc_pos->data.coef += ele.coef;                         //改变当前结点系数的值
        if (!loc_pos->data.coef) {                              //系数为 0
            //删除多项式 L 中当前结点
            prior_pos = PriorPos(link_list, loc_pos);                           //s为当前结点的前驱
            if (!prior_pos) //pos 无前驱，说明就一个结点，所以需要 s 变成当前结点的前驱（即头结点）
                prior_pos = link_list.head;
            DelFirstP(link_list, prior_pos, loc_pos);
            FreeNode(loc_pos);
        }
    } else {                                                //L 中不存在该指数项，生成该指数项并插入链表
        MakeNode(prior_pos, ele); //生成结点
        InsFirstP(link_list, loc_pos, prior_pos);       //根据 loc_pos 插入结点，正好插入在 loc_pos 之后
    }
}


//书上都是 DelFirst，改成 DelFirstP
//该算法是拿两个指针依次对比 Pa 和 Pb 的元素，步骤如下:
// 1. 如果 Pa 指针当前指向的元素指数小，则向前移动 Pa 指针
// 2. 如果 Pb 指针当前指向的元素指数小，则移除 pb 当前的结点并添加到 Pa 中，++ Pa.len; -- Pb.len;
// 3. 如果 Pa 指针和 Pb 指针当前指向的元素指数相同，则对这两个结点的系数进行运算，并从 Pb 中移除当前结点, -- Pb.len
void AddPolyn(polynomial &Pa, polynomial &Pb) {

    //多项式加法：Pa = Pa + Pb，利用两个多项式的结点构成 “和多项式"
    Position poly_a_head_pos, poly_b_head_pos, poly_a_next_pos, poly_b_next_pos;

    poly_a_head_pos = GetHead(Pa);
    poly_b_head_pos = GetHead(Pb);                                     //ha 和 hb 分别指向 Pa 和 Pb 的头结点，ha 一直在 qa 的前一个结点
    poly_a_next_pos = NextPos(Pa, poly_a_head_pos);
    poly_b_next_pos = NextPos(Pb, poly_b_head_pos);                    //qa 和 qb 分别指向 Pa 和 Pb 中当前结点

    while (poly_a_next_pos && poly_b_next_pos) {                       //qa 和 qb 均非空
        ElemType a = GetCurElem(poly_a_next_pos);
        ElemType b = GetCurElem(poly_b_next_pos);                      //a 和 b 为两表中当前比较元素

        switch (cmp(a, b)) {                              //比较两者的指数

            case -1:                                      //多项式 PA 中当前结点的指数值小
                poly_a_head_pos = poly_a_next_pos;
                poly_a_next_pos = NextPos(Pa, poly_a_next_pos);
                break;

            case 0: {                                     //两者的指数值相等

                float sum = a.coef + b.coef;              //将两者系数相加，放到一个新结点里
                if (sum != 0.0) {                         //如果 两结点相加的结果系数不为 0 则修改多项式 PA 中当前结点的值为 tempElemType
                    ElemType tempElemType;
                    tempElemType.coef = sum;              //新结点的系数就是这两个结点系数的和
                    tempElemType.expn = a.expn;
                    SetCurElem(poly_a_next_pos, tempElemType);
                    poly_a_head_pos = poly_a_next_pos;
                } else {                                  //如果 两结点相加的结果系数为 0 则删除多项式 PA 中当前结点
                    DelFirstP(Pa, poly_a_head_pos, poly_a_next_pos);
                    FreeNode(poly_a_next_pos);
                }

                DelFirstP(Pb, poly_b_head_pos,
                          poly_b_next_pos);                           //因为当前 b 结点和当前 a 结点指数相同，处理了 a 结点删掉 b 结点即可
                FreeNode(poly_b_next_pos);

                poly_b_next_pos = NextPos(Pb, poly_b_head_pos);
                poly_a_next_pos = NextPos(Pa,
                                          poly_a_head_pos);              //指数相等 ha 不变, qa 继续指向下一个, ------- case 1 不处理 qa ??

                break;
            }
            case 1:                                                     //多项式 PB 中当前结点的指数值小

                //当前qa 是比 pb 当前结点指数大的，所以要将删除掉的 qb 所指向的结点插入 qa 前面的结点 ha 的第一个结点之前(正好是 qa 的结点之前)
                DelFirstP(Pb, poly_b_head_pos, poly_b_next_pos);
                InsFirstP(Pa, poly_a_head_pos, poly_b_next_pos);

                poly_b_next_pos = NextPos(Pb, poly_b_head_pos);         //因为移除了一个结点，所以 qb 被赋值为头结点 hb 的下一个结点
                poly_a_head_pos = NextPos(Pa,
                                          poly_a_head_pos);             //把 pb 的指数值较小的结点插入后，ha 需要向后移动，但 qa 不用动，此时 ha 还是在 qa 前边

                break;

        }//switch
    }//while

    if (!ListEmpty(Pb)) {
        Append(Pa, poly_b_next_pos);                                //链接 Pb 中剩余结点
        DelFirstP(Pb, poly_b_head_pos, poly_b_next_pos);         //书上没有这段代码，但是不加执行完当前函数后 Pb 仍会有剩余结点
    }

    //看看 pb 是否是 empty,不是则修改 len,头尾指针置空

    FreeNode(poly_b_head_pos);                                      //释放 Pb 的头结点

}//Addpolyn

//该算法是依次遍历 Pb，拿出当前元素，依次插入并合并到 Pa 中
void AddPolyn1(polynomial &Pa, polynomial &Pb) {           //另一种多项式加法的算法：Pa = Pa + Pb，并销毁一元多项式Pb
    Position qb;
    term poly_b_cur_ele;
    qb = GetHead(Pb);                                      //qb 指向Pb的头结点
    qb = qb->next;                                         //qb 指向Pb的第1个结点
    while (qb) {
        poly_b_cur_ele = GetCurElem(qb);
        OrderInsertMerge(Pa, poly_b_cur_ele, cmp);
        qb = qb->next;
    }
    DestroyPolyn(Pb);                                      //销毁Pb
}

//一元多项式 Pa 系数取反(乘 -1)，
void Opposite(polynomial Pa) {                             //Opposite:对面的
    Position p;
    p = Pa.head;
    while (p->next) {
        p = p->next;
        p->data.coef *= -1;
    }
}


void SubtractPolyn(polynomial &Pa, polynomial &Pb) {        //多项式减法：Pa=Pa-Pb，并销毁一元多项式Pb
    Opposite(Pb);
    AddPolyn(Pa, Pb);
}


//多项式相乘就是 Pa 的每个结点依次乘 Pb 的每个结点，两个相乘的结点系数相乘，指数相加
void MultiplyPolyn(polynomial &Pa, polynomial &Pb) {        // 多项式乘法：Pa = Pa × Pb，并销毁一元多项式Pb
    polynomial Pc;
    Position poly_a_pos, poly_b_pos;
    term poly_a_ele, poly_b_ele, poly_c_ele;
    InitList(Pc);

    poly_a_pos = GetHead(Pa);
    poly_a_pos = poly_a_pos->next;

    while (poly_a_pos) {
        poly_a_ele = GetCurElem(poly_a_pos);

        poly_b_pos = GetHead(Pb);                           //因为每次都是 Pb 从头开始乘
        poly_b_pos = poly_b_pos->next;
        while (poly_b_pos) {
            poly_b_ele = GetCurElem(poly_b_pos);
            poly_c_ele.coef = poly_a_ele.coef * poly_b_ele.coef;
            poly_c_ele.expn = poly_a_ele.expn + poly_b_ele.expn;
            OrderInsertMerge(Pc, poly_c_ele, cmp);
            poly_b_pos = poly_b_pos->next;
        }
        poly_a_pos = poly_a_pos->next;
    }
    DestroyPolyn(Pb); // 销毁 Pb
    ClearList(Pa); // 将Pa重置为空表
    Pa.head = Pc.head;
    Pa.tail = Pc.tail;
    Pa.len = Pc.len;
}


void PrintPolyn(polynomial P) {                             //打印输出一元多项式P
    Link q;
    q = P.head->next;                                       //q 指向第1个结点
    printf(" 系数指数\n");
    while (q) {
        printf("%f %d\n", q->data.coef, q->data.expn);
        q = q->next;
    }
}

//若升序链表 L 中存在与 e 满足判定函数 compare() 取值为 0 的元素，则 q 指示 L 中第一个值为 e 的结点的位置，并返回TRUE；
//否则 q 指示第一个与 e 满足判定函数 compare() 取值 > 0 的元素的前驱的位置，并返回 FALSE（用于一元多项式）
Status LocateElemP(LinkList L, ElemType e, Position &param_pos, int(*compare)(ElemType, ElemType)) {
    Link link = L.head, link_last_pos;
    do {
        link_last_pos = link;
        link = link->next;
    } while (link && (compare(link->data, e) < 0));         //没到表尾且 p->data.expn < e.expn

    //到表尾 或 compare(p->data,e)>0   //compare(link->data, e) 说明 link->data 的指数大
    if (!link || compare(link->data, e) > 0) {
        param_pos = link_last_pos;                           //此时 param_pos 是 link 的前一个结点（该结点的指数比 e 小），
        // 即返回的 param_pos 满足 link 之前的结点 compare() < 0，之后的结点(包括 link) compare() > 0，从而如果在 param_pos 插入结点则正好满足链表从小到大排列
        return ERROR;
    } else {                                                //找到，没到表尾且 (compare( p->data, e) = 0 即 p->data.expn = e.expn
        param_pos = link;
        return OK;
    }
}//LocateElemP


Status OrderInsert(LinkList *L, ElemType e, int(*comp)(ElemType, ElemType)) {
    /* 已知L为有序线性链表，将元素e按非降序插入在L中。（用于一元多项式） */
    Link o, p, q;
    q = (*L).head;
    p = q->next;
    while (p != NULL && comp(p->data, e) < 0) /* p不是表尾且元素值小于e */
    {
        q = p;
        p = p->next;
    }
    o = (Link) malloc(sizeof(LNode)); /* 生成结点 */
    o->data = e; /* 赋值 */
    q->next = o; /* 插入 */
    o->next = p;
    (*L).len++; /* 表长加1 */
    if (!p) /* 插在表尾 */
        (*L).tail = o; /* 修改尾结点 */
    return OK;
}

